import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *
 * 回文串 是正着读和反着读都一样的字符串。
 */
public class Test131 {

    public static void main(String[] args) {
        List<List<String>> ret = partition("aab");
        System.out.println(ret);
    }


    static List<List<String>> ret = new ArrayList<>();
    static List<String> list = new ArrayList<>();
    static boolean[][] dp;
    static int len;
    public static List<List<String>> partition(String s) {
        len = s.length();
        dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len; j++) {
                int right = j+i;
                if (right >= len) break;
                if (i == 1){
                    dp[j][right] = s.charAt(j)==s.charAt(right);
                }else{
                    dp[j][right] = dp[j+1][right-1] && s.charAt(j)==s.charAt(right);
                }
            }
        }
        dfs(s,0);
        return ret;
    }
    public static void dfs(String s,int start){
        if (start == len){
            ret.add(new ArrayList<>(list));
        }
        for (int end = start; end < len; end++) {
            if (dp[start][end]){
                list.add(s.substring(start,end+1));
                dfs(s,end+1);
                list.remove(list.size()-1);
            }
        }
    }
}















